package com.qz.recursion;

/**
 * @Description n皇后问题
 * @Author Flag
 * @Date: 2021/7/26 9:07
 * @Version: 1.0
 **/
public class Queue8Dome {
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8(8);
        queue8.check(0);
    }


}


class Queue8{
    //定义一个max表示一共有多少个皇后
    private int max;
    //定义数组array，保存皇后放置位置的结果，比如arr= {0,4,7,5,2,6,1,3}
    //存储是行号，每一个arrary[]的值表示列数
    private int[] array;

    static int count;
    /**
     * 构造方法
     * @param max
     */
    public Queue8(int max) {
        this.max = max;
        this.array = new int[8];
        int index = 0;
        while (index <max){
            array[index] = -1;
            index++;
        }
    }



    /**
     * 写一个方法，可以将皇后摆放的位置输出
     */
    public void show(){
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
        count++;
        System.out.println("数量:"+count);
    }


    /**
     * 查看当前我们放置第n个皇后，就去检测皇后是否和前面已经摆放的皇后产生冲突
     * @param n 表示第n个皇后，
     * @return
     */
    private boolean judeg(int n){
        for (int i = 0; i < n; i++) {
            /**
             * 说明：
             * array[i] == array[n]，表示在同一列
             *      因为：本身array是一个一维数组，并且循环遍历i表示行数，arraay[i]的值表示在第几列(从0开始),
             *      假设：当进入方法时候,n已经是确定值，表示行，并且array[n]也是一个确定值,表示列
             *      如果当i=n的时候，此时的array[i] == array[n]肯定相等，
             *      如果当arrary[i] == array[n]相等时,说明第i列的皇后在第array[i]行上，第n列也在array[n]上，因为相同，所以同一行了
             * Math.abs(n-i) == Math.abs(array[n] -array[i]) 表示同一斜线
             *      因为如果两个点在同一个斜线上，则以两个点为对点会形成一个正方形
             *      只需要证明两条临边是否相等，如果相等就是正方形
             */
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] -array[i])){
                return false;
            }
        }
        return true;
    }


    /**
     * 编写一个方法，放置第n个皇后
     * @param n
     */
    public void check(int n){
        //如果n=max,表示当前要求的数量已经放好，因为n从0开始
        if(n == max){
          show();
          return;
        }
        //依次放入
        for (int i = 0; i < max; i++) {
            //先把当前皇后n放到该行的第一列
            array[n] = i;
            //判断当放置第n个皇后到i列，是否冲突
            if(judeg(n)){
                //不冲突
                check(n+1);
            }
            //如果冲突，就继续执行array[n]=i,即使第n个皇后，放置到本行得后移一个位置

        }
    }


}